package com.alice.router.utils;

import java.util.*;
import java.util.concurrent.atomic.AtomicReference;

/**
 * 排序工具类
 */
public class SortUtil {
    //选择排序用时：25410 200000
    public static List<Integer> selectSort(List<Integer> array){
        for (int i = 0; i < array.size(); i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.size(); j++) {
                if (array.get(minIndex) > array.get(j)) {
                    minIndex = j;
                }
            }
            int temp = array.get(i);
            array.set(i, array.get(minIndex));
            array.set(minIndex, temp);
        }
        return array;
    }

    /**
     * 插入排序：插入元素与列表尾部比较，插入元素比其小，其后移一位，直到找到列表元素比它小的，
     * 则该元素的位置加一为插入元素的位置
     * @param array
     * @return
     */
    public static List<Integer> insertSort(List<Integer> array) {
        for (int i = 1; i < array.size(); i++) {
            Integer element = array.get(i);
            int j = i - 1;
            for (; j > 0; ) {
                if (element < array.get(j)) {
                    array.set(j + 1, array.get(j));
                    j--;
                } else {
                    break;
                }
            }
            array.set(j + 1, element);
        }
        return array;
    }

    public static void mergeSort(List<Integer> array,int p,int r){
        System.out.println("mergeSort: p=" + p + " ,r=" + r);
        if (p < r) {
            int q = (p + r) / 2;
//            System.out.println("mergeSort: p=" + p + " ,q=" + q + " ,r=" + r);
//            System.out.println("----------mergeSort(array,p,q);--------------");
            mergeSort(array, p, q);
//            System.out.println("mergeSort: p=" + p + " ,q=" + q + " ,r=" + r);
//            System.out.println("----------mergeSort(array,q+1,r);--------------");
            mergeSort(array, q + 1, r);
//            System.out.println("mergeSort: p=" + p + " ,q=" + q + " ,r=" + r);
//            System.out.println("----------mergeList(array,p,q,r);--------------");
            mergeList(array, p, q, r);
        }
    }

    /**
     * 踩坑：subList获得的只是原列表的视图，操作subList也会改变原列表
     * @param array
     * @param p
     * @param q
     * @param r
     * @return
     */
    public static List<Integer> mergeList(List<Integer> array, int p, int q, int r) {
        System.out.println("mergeList: p=" + p + " ,q=" + q + " ,r=" + r);
        List<Integer> subList1 = new ArrayList<>();
        List<Integer> subList2 = new ArrayList<>();
        for (int i = p; i < q; i++) {
            subList1.add(array.get(i));
        }
        for (int i = q; i < r; i++) {
            subList2.add(array.get(i));
        }
        int i = 0, j = 0;
        for (int k = p; k < r; k++) {
            if (i >= subList1.size() && j < subList2.size()) {
                array.set(k, subList2.get(j));
                printList(array);
                j++;
                continue;
            }
            if (j >= subList2.size() && i < subList1.size()) {
                array.set(k, subList1.get(i));
                printList(array);
                i++;
                continue;
            }
            if (i < subList1.size() && j < subList2.size()) {
                if (subList1.get(i) <= subList2.get(j)) {
                    array.set(k, subList1.get(i));
                    printList(array);
                    i++;
                } else {
                    array.set(k, subList2.get(j));
                    printList(array);
                    j++;
                }
            }
        }
        return array;
    }

    public static Queue<Integer> quickSort(List<Integer> array){
        Queue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < array.size(); i++) {
            queue.add(array.get(i));
        }
        return queue;
    }

    public static void printList(List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.printf("%d,", list.get(i));
        }
        System.out.println();
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int[] array = new int[20];
        Random random = new Random(1);
        for (int i = 0; i < 20; i++) {
            list.add(random.nextInt(i+1));
            array[i]=random.nextInt(i+1);
        }
        list = Arrays.asList(5, 2, 4, 7, 1, 3, 2, 6);

        printList(list);
        long startTime = System.currentTimeMillis();
//        List<Integer> list1 = insertSort(list);
        mergeSort(list,0,8);
//        Queue<Integer> queue = quickSort(list);
        //List<Integer> integers = selectSort(list);
        ////选择排序+桶排序用时：2140853 2000000数据
        //List<Integer> sort1 = SortUtil.selectSort(list1);
//        List<Integer> sort2 = SortUtil.selectSort(list2);
//        List<Integer> sort3 = SortUtil.selectSort(list3);
//        List<Integer> sort4 = SortUtil.selectSort(list4);
//        List<Integer> sort5 = SortUtil.selectSort(list5);
//        List<Integer> sort6 = SortUtil.selectSort(list6);
//        List<Integer> sort7 = SortUtil.selectSort(list7);
//        List<Integer> sort8 = SortUtil.selectSort(list8);
//        List<Integer> sort9 = SortUtil.selectSort(list9);

        long endTime = System.currentTimeMillis();

//        System.out.println("选择排序用时："+(endTime-startTime));
        System.out.println("插入排序用时："+(endTime-startTime));
//        for (int i = 0; i < queue.size(); i++) {
//            System.out.printf("%d,",queue.poll());
//        }
        for (int i = 0; i < list.size(); i++) {
            System.out.printf("%d,",list.get(i));
        }
    }
}
